1. Field of the Invention
The present invention relates to a method, system and program for decoding a section of output from compressed data.
2. Description of the Related Art
Digital images may use one or more bits to describe the color intensity at each pixel. The term “pixel” as used herein refers to one or more intensity or bit values at a data point that represents data to be rendered (i.e., printed, displayed, etc.), where the data to be rendered may include, but is not limited to, images, text, composite images, graphs, collages, scientific data, video, etc. A pel is a picture element point that may be expressed with one bit. If only one bit is used to express the intensity, then the image is a bilevel image where there are two possible intensity values per pixel, such as black and white or fill saturation and no intensity. Digital monochrome images that allow for more than two intensities per pixel express the intensities as shades of grey.
Most systems compress image data before transmitting the data to an output device, such as a printer or display, that renders the image data. The output device must decode or decompress the compressed image to output to print or otherwise render it. Compressed images may also be archived and then at some later time transmitted to an output device for decompression and rendering, e.g., printing or display.
Compression has become especially important as the resolution of digital images continues to increase, which has substantially increased the size of the digital image files. Data compression was essential to allowing digital facsimile transmission to become practical. Three international standards for facsimile data compression include the G3 standard Modified Huffman (MH), the G3 Modified READ (MR), and the G4 Modified Modified Read (MMR). G3 MH codes each line independently with one-dimensional run lengths alternating between “white” and “black” Huffman code tables. G3 MR codes at least every second or fourth line with G3 MH. The rest of the lines are coded relative to its preceding line using vertical reference codes out to plus or minus three whenever possible. Otherwise a run prefix is followed by a pair of runs coded with the MH tables. Pairs of runs on the preceding line are skipped over with a PASS code. G4 MMR compresses image data by assuming an all white history line before the top image line and encodes all lines two-dimensionally with reference to a history line, i.e., the same coding used for the G3 MR two-dimensional lines. The G4 MMR decoder must maintain an entire previous history line when decompressing data to sequentially decode the entire image. G3 MH allows random access to each line if a pointer is kept to the end-of-line (EOL) codes. G3 MR allows random access only for those EOLs that are followed by MH coded lines. G4 MMR does not have EOLs between compressed lines and so does not allow anything but sequential decoding from the top of the image.
Another image decoding technique is the Adaptive Bi-Level Image Compression (ABIC) algorithm. An ABIC coder uses arithmetic coding to code an image as a bi-level image. The ABIC algorithm of the prior art would sequentially code each bit of image data by using the seven nearest neighbor bits and a probability distribution that is calculated based on previously coded data. In current implementations, the ABIC decoder maintains a history group of bits comprising the last N+2 decoded bits, where N is the length of a line. In certain current implementations, the ABIC decoder uses seven of the bits, including the last two decoded bits and bits in the history range from the (N−2) bit to the (N+2) bit. These are the seven nearest bits in the binary image. Details of using the ABIC algorithm to code and decode data are described in the IBM publication entitled “A Multi-Purpose VLSI Chip for Adaptive Data Compression of Bilevel Images”, by R. B. Arps, T. K. Truong, D. J. Lu, R. C. Pasco, and T. D. Friedman, IBM J. Res. Develop., Vol. 32, No. 6, pgs. 775-795 (November 1988) and the commonly assigned U.S. Pat. No. 4,905,297, which publication and patent are incorporated herein by reference in their entirety.
In certain cases, a user may only want to access a section of an image, such as a cropped portion of an image, cut out, etc. With prior art techniques, to access an image section, the ABIC and G4 MMR decoders must decode and buffer the entire previous history line prior to the current line, and then buffer and use the previous history line to decode the next line. Such techniques must entirely decode and buffer each line even though only a section of the line is needed. As digital image resolution and file size increases, the processing and memory resources and time needed to buffer each line of decoded data and decode each line to access only a section of the image likewise increases.
Accordingly, there is a need in the art for techniques to improve the image decoding process.